<!DOCTYPE html>
<html lang="zh-cn">
    <head><meta charset='utf-8'>
<meta name='viewport' content='width=device-width, initial-scale=1'><meta name='description' content='整理竞赛中可能会用到的STL代码和性质'><title>竞赛用STL整理</title>

<link rel='canonical' href='https://luobo.cf/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/'>

<link rel="stylesheet" href="/scss/style.min.css"><meta property='og:title' content='竞赛用STL整理'>
<meta property='og:description' content='整理竞赛中可能会用到的STL代码和性质'>
<meta property='og:url' content='https://luobo.cf/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/'>
<meta property='og:site_name' content='luoboQAQ'>
<meta property='og:type' content='article'><meta property='article:section' content='Post' /><meta property='article:tag' content='C&#43;&#43;' /><meta property='article:published_time' content='2021-01-31T20:39:29&#43;08:00'/><meta property='article:modified_time' content='2021-02-01T12:00:00&#43;08:00'/><meta property='og:image' content='https://luobo.cf/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/85526504.jpg' />
<meta name="twitter:title" content="竞赛用STL整理">
<meta name="twitter:description" content="整理竞赛中可能会用到的STL代码和性质"><meta name="twitter:card" content="summary_large_image">
    <meta name="twitter:image" content='https://luobo.cf/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/85526504.jpg' />
    </head>
    <body class="
    article-page has-toc
">
    <script>
        (function() {
            const colorSchemeKey = 'StackColorScheme';
            if(!localStorage.getItem(colorSchemeKey)){
                localStorage.setItem(colorSchemeKey, "auto");
            }
        })();
    </script><script>
    (function() {
        const colorSchemeKey = 'StackColorScheme';
        const colorSchemeItem = localStorage.getItem(colorSchemeKey);
        const supportDarkMode = window.matchMedia('(prefers-color-scheme: dark)').matches === true;

        if (colorSchemeItem == 'dark' || colorSchemeItem === 'auto' && supportDarkMode) {
            

            document.documentElement.dataset.scheme = 'dark';
        } else {
            document.documentElement.dataset.scheme = 'light';
        }
    })();
</script>
<div class="container main-container flex 
    
        extended
    
">
    
        <div id="article-toolbar">
            <a href="https://luobo.cf" class="back-home">
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-chevron-left" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <polyline points="15 6 9 12 15 18" />
</svg>



                <span>返回</span>
            </a>
        </div>
    
<main class="main full-width">
    <article class="has-image main-article">
    <header class="article-header">
        <div class="article-image">
            <a href="/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/">
                <img src="/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/85526504_huffc36122ca7f2f624d334d6d5c5a83e7_1825704_800x0_resize_q75_box.jpg"
                        srcset="/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/85526504_huffc36122ca7f2f624d334d6d5c5a83e7_1825704_800x0_resize_q75_box.jpg 800w, /p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/85526504_huffc36122ca7f2f624d334d6d5c5a83e7_1825704_1600x0_resize_q75_box.jpg 1600w"
                        width="800" 
                        height="346" 
                        loading="lazy"
                        alt="Featured image of post 竞赛用STL整理" />
                
            </a>
        </div>
    

    <div class="article-details">
    

    <h2 class="article-title">
        <a href="/p/%E7%AB%9E%E8%B5%9B%E7%94%A8stl%E6%95%B4%E7%90%86/">竞赛用STL整理</a>
    </h2>

    
    <h3 class="article-subtitle">
        整理竞赛中可能会用到的STL代码和性质
    </h3>
    

    
    <footer class="article-time">
        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-calendar-time" width="56" height="56" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <path d="M11.795 21h-6.795a2 2 0 0 1 -2 -2v-12a2 2 0 0 1 2 -2h12a2 2 0 0 1 2 2v4" />
  <circle cx="18" cy="18" r="4" />
  <path d="M15 3v4" />
  <path d="M7 3v4" />
  <path d="M3 11h16" />
  <path d="M18 16.496v1.504l1 1" />
</svg>
                <time class="article-time--published">Jan 31, 2021</time>
            </div>
        

        
            <div>
                <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



                <time class="article-time--reading">
                    阅读时长: 1 分钟
                </time>
            </div>
        
    </footer>
    
</div>
</header>

    <section class="article-content">
    <p>最近刷了好几道关于STL的竞赛题，许多知识点还是不熟练，在继续学习之前，还是来好好整理一下一些常见的STL和容器吧。紫书上介绍的有以下几种：</p>
<ul>
<li>线性：<code>vector</code>,<code>list</code>,<code>string</code></li>
<li>关联：<code>map,set</code></li>
<li>特殊：<code>stack,queue,priority_queue</code></li>
<li>算法：<code>sort,lower_bound,find</code></li>
</ul>
<h2 id="vector">vector</h2>
<p>vector可以理解为可以自由变换长度的数组(不定长数组)，个人感觉使用频率还是很高的。vector是连续的，意味着可以使用<code>[]</code>或<code>at()</code>。</p>
<p><strong>声明：</strong> <code>vector&lt;int&gt; a</code></p>
<h3 id="常用函数">常用函数</h3>
<ul>
<li>
<p>push_back：在尾部添加一个数据</p>
</li>
<li>
<p>pop_back：删除尾部的一个数据</p>
</li>
<li>
<p>size：当前的大小（就是有多少元素）</p>
</li>
<li>
<p>erase：删除指针指向的数据项</p>
</li>
<li>
<p>clear：清空</p>
</li>
<li>
<p>empty：判断是否为空</p>
</li>
</ul>
<h2 id="deque">deque</h2>
<p>deque可以看作是双向队列，是<strong>连续</strong>存储结构。vector有的功能它都有，还支持高效的首/尾端插入/删除操作。</p>
<h3 id="新增函数">新增函数</h3>
<ul>
<li>push_front：在头部添加一个数据</li>
<li>pop_front：在头部删除一个数据</li>
</ul>
<h2 id="list">list</h2>
<p>list可以看作是双链表，是<strong>非连续</strong>存储结构。可在两端进行push、pop，同时在内部可以很方便的进行插入和删除操作。不过我没怎么用到这个容器。等我做到相关的题目再来补充一些信息吧。</p>
<h2 id="string">string</h2>
<p>string就是字符串。相比char[]那可是方便不少，c++的cin/cout就只支持string类型而不支持char型数组。string还支持<code>+、=、+=</code>等运算符。</p>
<h3 id="常用函数-1">常用函数</h3>
<ul>
<li>
<p>append：在字符串后添加（相当于+=）</p>
</li>
<li>
<p>substr(n,m)：返回string的子串，从n处开始，取m个。当m省略或超过了字符串的长度，则一直取到字符串结束。</p>
</li>
</ul>
<p><strong>查找相关函数</strong>：</p>
<p>如果没有查到，返回string::npos。</p>
<ul>
<li>
<p>find：从前往后查找子串或字符出现的位置。</p>
</li>
<li>
<p>rfind：从后往前查找子串或字符出现的位置。</p>
</li>
<li>
<p>find_first_of：从前往后查找何处出现另一个字符串中包含的字符。例如：</p>
</li>
<li>
<p>s1.find_first_of(&ldquo;abc&rdquo;); //查找s1中第一次出现&quot;abc&quot;中任一字符的位置</p>
</li>
<li>
<p>find_last_of：从后往前查找何处出现另一个字符串中包含的字符。</p>
</li>
<li>
<p>find_first_not_of：从前往后查找何处出现另一个字符串中没有包含的字符。</p>
</li>
<li>
<p>find_last_not_of：从后往前查找何处出现另一个字符串中没有包含的字符。</p>
</li>
</ul>
<h3 id="流处理">流处理</h3>
<p>可以通过<code>&lt;sstream&gt;</code>，将string对象作为一个流。例如：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="cp">#include</span> <span class="cpf">&lt;iostream&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;sstream&gt;</span><span class="cp">
</span><span class="cp">#include</span> <span class="cpf">&lt;string&gt;</span><span class="cp">
</span><span class="cp"></span><span class="k">using</span> <span class="k">namespace</span> <span class="n">std</span><span class="p">;</span>

<span class="kt">int</span> <span class="nf">main</span><span class="p">(){</span>
    <span class="n">string</span> <span class="n">line</span><span class="p">;</span>
    <span class="k">while</span><span class="p">(</span><span class="n">getline</span><span class="p">(</span><span class="n">cin</span><span class="p">,</span><span class="n">line</span><span class="p">)){</span>
        <span class="n">stringstream</span> <span class="n">ss</span><span class="p">(</span><span class="n">line</span><span class="p">);</span>
        <span class="k">while</span><span class="p">(</span><span class="n">ss</span><span class="o">&gt;&gt;</span><span class="n">x</span><span class="p">){...}</span>
    <span class="p">}</span>
<span class="p">}</span>
</code></pre></div><h2 id="set">set</h2>
<p>set就是数学中的集合，每个元素只能出现一次，set中的元素已经从小到大排好了。</p>
<h3 id="常用函数-2">常用函数</h3>
<ul>
<li>insert：插入一个元素</li>
<li>erase：删除，可以传入定位器，也可直接传入值</li>
<li>count：统计元素出现的个数，因为只有0/1个，所以一般用来判断元素是否存在</li>
<li>find：查找</li>
</ul>
<p>对于自己定义的结构体，需要重载&lt;运算符。</p>
<h3 id="常用算法">常用算法</h3>
<p>在<code>&lt;algorithm&gt;</code>中提供了关于set的两种算法（目前只知道两种）</p>
<ol>
<li>
<p>set_union：取两个集合的并集，例如：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="cp">#define ALL(x) x.begin(),x.end()
</span><span class="cp">#define INS(x) inserter(x,x.begin())
</span><span class="cp"></span><span class="n">set_union</span><span class="p">(</span><span class="n">ALL</span><span class="p">(</span><span class="n">x1</span><span class="p">),</span><span class="n">ALL</span><span class="p">(</span><span class="n">x2</span><span class="p">),</span><span class="n">INS</span><span class="p">(</span><span class="n">x</span><span class="p">));</span> <span class="c1">//将x1和x2的内容取并集后放入x中
</span></code></pre></div></li>
<li>
<p>set_intersection：取两个集合的交集，例如：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="n">set_intersection</span><span class="p">(</span><span class="n">ALL</span><span class="p">(</span><span class="n">x1</span><span class="p">),</span><span class="n">ALL</span><span class="p">(</span><span class="n">x2</span><span class="p">),</span><span class="n">INS</span><span class="p">(</span><span class="n">x</span><span class="p">));</span> <span class="c1">//将x1和x2的内容取交集放入x中
</span></code></pre></div></li>
</ol>
<h2 id="map">map</h2>
<p>map是映射，支持[]运算符，还是非常实用的。</p>
<p>map的函数和set基本一致，这里就不重复写了。</p>
<h2 id="stack">stack</h2>
<p>stack就是数据结构中的栈，数据是“后进先出”。</p>
<h3 id="基本函数">基本函数</h3>
<ul>
<li>push：入栈</li>
<li>pop：出栈</li>
<li>top：取栈顶元素</li>
</ul>
<p>要注意的是，使用pop()出栈并不会返回被删除的元素值，如果想要需要先top()一下</p>
<h2 id="queue">queue</h2>
<p>queue就是数据结构里的队列，数据符合“先进先出”的规则。</p>
<h3 id="基本函数-1">基本函数</h3>
<ul>
<li>
<p>push：入队</p>
</li>
<li>
<p>pop：出队</p>
</li>
<li>
<p>front：取队首</p>
</li>
</ul>
<h3 id="priority_queue">priority_queue</h3>
<p>优先队列，将按照优先级来排序，取队首的<code>front()</code>的函数将换为<code>top()</code>。该容器也定义在头文件<code>&lt;queue&gt;</code>里。</p>
<p>对于自定义数据类型的队列，需要定义<code>&lt;</code>运算。对于已经定义过的数据类型，我们可以通过定义一个结构体，在其中重载<code>()</code>运算符来看起来像一个函数，例如：</p>
<div class="highlight"><pre tabindex="0" class="chroma"><code class="language-c++" data-lang="c++"><span class="k">struct</span> <span class="nc">cmp</span>
<span class="p">{</span>
    <span class="kt">bool</span> <span class="nf">operator</span><span class="p">()(</span><span class="k">const</span> <span class="kt">int</span> <span class="n">a</span><span class="p">,</span> <span class="k">const</span> <span class="kt">int</span> <span class="n">b</span><span class="p">)</span> <span class="k">const</span>
    <span class="p">{</span>
        <span class="k">return</span> <span class="n">abs</span><span class="p">(</span><span class="n">a</span><span class="p">)</span> <span class="o">&lt;</span> <span class="n">abs</span><span class="p">(</span><span class="n">b</span><span class="p">);</span>
    <span class="p">}</span>
<span class="p">};</span>
<span class="n">priority_queue</span><span class="o">&lt;</span><span class="kt">int</span><span class="p">,</span> <span class="n">vector</span><span class="o">&lt;</span><span class="kt">int</span><span class="o">&gt;</span><span class="p">,</span> <span class="n">cmp</span><span class="o">&gt;</span> <span class="n">p_queue</span><span class="p">;</span>
</code></pre></div><p>这样就定义了一个绝对值大小优先的队列</p>

</section>


    <footer class="article-footer">
    
    <section class="article-tags">
        
            <a href="/tags/c&#43;&#43;/">C&#43;&#43;</a>
        
    </section>


    
    <section class="article-copyright">
        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-copyright" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <path d="M14.5 9a3.5 4 0 1 0 0 6" />
</svg>



        <span>Licensed under CC BY-NC-SA 4.0</span>
    </section>
    <section class="article-time">
        <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-clock" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <circle cx="12" cy="12" r="9" />
  <polyline points="12 7 12 12 15 15" />
</svg>



        <span class="article-time--modified">
            最后更新于 Feb 01, 2021 12:00 &#43;0800
        </span>
    </section></footer>


    
</article>

    <aside class="related-contents--wrapper">
    
    
</aside>

     
     
        
    

    <footer class="site-footer">
    <section class="copyright">
        &copy; 
        
            2020 - 
        
        2021 luoboQAQ
    </section>
    
    <section class="powerby">
        Built with <a href="https://gohugo.io/" target="_blank" rel="noopener">Hugo</a> <br />
        Theme <b><a href="https://github.com/CaiJimmy/hugo-theme-stack" target="_blank" rel="noopener" data-version="3.0.0">Stack</a></b> designed by <a href="https://jimmycai.com" target="_blank" rel="noopener">Jimmy</a>
    </section>
</footer>

    
<div class="pswp" tabindex="-1" role="dialog" aria-hidden="true">

    
    <div class="pswp__bg"></div>

    
    <div class="pswp__scroll-wrap">

        
        <div class="pswp__container">
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
            <div class="pswp__item"></div>
        </div>

        
        <div class="pswp__ui pswp__ui--hidden">

            <div class="pswp__top-bar">

                

                <div class="pswp__counter"></div>

                <button class="pswp__button pswp__button--close" title="Close (Esc)"></button>

                <button class="pswp__button pswp__button--share" title="Share"></button>

                <button class="pswp__button pswp__button--fs" title="Toggle fullscreen"></button>

                <button class="pswp__button pswp__button--zoom" title="Zoom in/out"></button>

                
                
                <div class="pswp__preloader">
                    <div class="pswp__preloader__icn">
                        <div class="pswp__preloader__cut">
                            <div class="pswp__preloader__donut"></div>
                        </div>
                    </div>
                </div>
            </div>

            <div class="pswp__share-modal pswp__share-modal--hidden pswp__single-tap">
                <div class="pswp__share-tooltip"></div>
            </div>

            <button class="pswp__button pswp__button--arrow--left" title="Previous (arrow left)">
            </button>

            <button class="pswp__button pswp__button--arrow--right" title="Next (arrow right)">
            </button>

            <div class="pswp__caption">
                <div class="pswp__caption__center"></div>
            </div>

        </div>

    </div>

</div><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.min.js"integrity="sha256-ePwmChbbvXbsO02lbM3HoHbSHTHFAeChekF1xKJdleo="crossorigin="anonymous"
                defer="true"
                >
            </script><script 
                src="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe-ui-default.min.js"integrity="sha256-UKkzOn/w1mBxRmLLGrSeyB4e1xbrp4xylgAWb3M42pU="crossorigin="anonymous"
                defer="true"
                >
            </script><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/default-skin/default-skin.css"integrity="sha256-c0uckgykQ9v5k&#43;IqViZOZKc47Jn7KQil4/MP3ySA3F8="crossorigin="anonymous"
            ><link 
                rel="stylesheet" 
                href="https://cdn.jsdelivr.net/npm/photoswipe@4.1.3/dist/photoswipe.css"integrity="sha256-SBLU4vv6CA6lHsZ1XyTdhyjJxCjPif/TRkjnsyGAGnE="crossorigin="anonymous"
            >

            </main>
    
        <aside class="sidebar right-sidebar sticky">
            <section class="widget archives">
                <div class="widget-icon">
                    <svg xmlns="http://www.w3.org/2000/svg" class="icon icon-tabler icon-tabler-hash" width="24" height="24" viewBox="0 0 24 24" stroke-width="2" stroke="currentColor" fill="none" stroke-linecap="round" stroke-linejoin="round">
  <path stroke="none" d="M0 0h24v24H0z"/>
  <line x1="5" y1="9" x2="19" y2="9" />
  <line x1="5" y1="15" x2="19" y2="15" />
  <line x1="11" y1="4" x2="7" y2="20" />
  <line x1="17" y1="4" x2="13" y2="20" />
</svg>



                </div>
                <h2 class="widget-title section-title">目录</h2>
                
                <div class="widget--toc">
                    <nav id="TableOfContents">
  <ol>
    <li><a href="#vector">vector</a>
      <ol>
        <li><a href="#常用函数">常用函数</a></li>
      </ol>
    </li>
    <li><a href="#deque">deque</a>
      <ol>
        <li><a href="#新增函数">新增函数</a></li>
      </ol>
    </li>
    <li><a href="#list">list</a></li>
    <li><a href="#string">string</a>
      <ol>
        <li><a href="#常用函数-1">常用函数</a></li>
        <li><a href="#流处理">流处理</a></li>
      </ol>
    </li>
    <li><a href="#set">set</a>
      <ol>
        <li><a href="#常用函数-2">常用函数</a></li>
        <li><a href="#常用算法">常用算法</a></li>
      </ol>
    </li>
    <li><a href="#map">map</a></li>
    <li><a href="#stack">stack</a>
      <ol>
        <li><a href="#基本函数">基本函数</a></li>
      </ol>
    </li>
    <li><a href="#queue">queue</a>
      <ol>
        <li><a href="#基本函数-1">基本函数</a></li>
        <li><a href="#priority_queue">priority_queue</a></li>
      </ol>
    </li>
  </ol>
</nav>
                </div>
            </section>
        </aside>
    

        </div>
        <script 
                src="https://cdn.jsdelivr.net/npm/node-vibrant@3.1.5/dist/vibrant.min.js"integrity="sha256-5NovOZc4iwiAWTYIFiIM7DxKUXKWvpVEuMEPLzcm5/g="crossorigin="anonymous"
                defer="false"
                >
            </script><script type="text/javascript" src="/ts/main.js" defer></script>
<script>
    (function () {
        const customFont = document.createElement('link');
        customFont.href = "https://fonts.googleapis.com/css2?family=Lato:wght@300;400;700&display=swap";

        customFont.type = "text/css";
        customFont.rel = "stylesheet";

        document.head.appendChild(customFont);
    }());
</script>

    </body>
</html>
